# -*- coding: utf-8 -*-

"""
Queue - 队列：
    一个FIFO（先进先出）的数据结构
    并发中使用较多，可以安全地将对象从一个任务传给另一个任务
"""

# same as list()
queue = []
size = len(queue)
queue.append(1)
queue.append(2)
# return 1
print(queue.pop(0))
# return 2 examine the first element
print(queue[0])

"""
方法说明：
    操作：方法
    Insert：queue.append(e)
    Remove：queue.pop(0)
    Examine：queue[0]
"""

"""
Priority Queue - 优先队列：
    优先队列中的每个元素都有各自的优先级
    优先级最高的元素最先得到服务
    优先级相同的元素按照其在优先队列中的顺序得到服务
    优先队列可以使用数组或链表实现，从时间和空间复杂度来说，往往用二叉堆来实现
方法说明：
    操作：方法：时间复杂度
    enqueue：heapq.push(queue, e)：O(log n)
    dequeue：heapq.pop(queue)：O(log n)
    init：heapq.heapify(queue)：O(nlog n)
    peek：queue[0]：O(1)
"""

"""
Deque - 双端队列：
    双端队列（deque，全名double-ended queue）
    可以在任何一端添加或者移除元素
    是一种具有队列和栈性质的数据结构

    Python的list就可以执行类似于deque的操作，但是效率会过于慢
    为了提升数据的处理效率，一些高效的数据结构放在了collections中
    在collections中提供了deque的类
    如果需要多次对list执行头尾元素的操作，请使用deque。
方法说明：
    操作：方法：时间复杂度
    enqueue left：dq.appendleft(e)：O(1)
    enqueue right：dq.append(e)：O(1)
    dequeue left：dq.popleft()：O(1)
    dequeue right：dq.pop()：O(1)
    peek left：dq[0]：O(1)
    peek right：dq[-1]：O(1)
"""